package com.mdnote.practice.dp;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/20
 * @description 爬楼梯 进阶
 */
public class LeetCode70Plus {

    /**
     * 爬楼梯，牛牛每次可以走1、2、3步，走前面两步不能喝第三步一样
     * 分析：
     * 1. 最优子结构： 走三步和走两步类似，probably(i) = probably(i - 1) + probably(i - 2) + probably(i - 3)
     *               我们需要多一个唯独去记录上一步走的是几步 probably(i， 0) -> 走到i阶台阶，上一步走的是1步的走法
     *                                                probably(i， 1) -> 走到i阶台阶，上一步走的是2步的走法
     *                                                probably(i， 2) -> 走到i阶台阶，上一步走的是3步的走法
     *               所以最后：probably(i， 0) = probably(i - 1， 1) + probably(i - 1)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  ， 2)
     *                       probably(i， 1) = probably(i - 2， 0) + probably(i， 2)
     *                       probably(i， 20 = probably(i - 3， 0) + probably(i， 1)
     * 2. DP数组： dp[i][j]  i 当前到达的台阶  j 最后一次垮了j步到台阶i
     * 3. DP方程：dp[i][0] = dp[i - 1][1] + do[i - 1][2]
     *           dp[i][1] = dp[i - 2][0] + dp[i - 1][2]
     *           dp[i][2] = dp[i - 3][0] + dp[i - 3][1]
     * @param n 台阶
     * @return 多少种走法
     */
    public int climbStairs(int n) {

        // 初始化DP数组
        int[][] dp = new int[n + 1][3];
        // 因为DP方程中存在i-3，我们要把0到2初始化好
        dp[0][0] = 1;
        dp[1][0] = 1;
        dp[2][1] = 1;
        dp[3][0] = 1;
        dp[3][1] = 1;
        dp[3][2] = 1;
        // 迭代
        for (int i = 4; i < dp.length; i++) {
            dp[i][0] = dp[i - 1][1] + dp[i - 1][2];
            dp[i][1] = dp[i - 2][0] + dp[i - 2][2];
            dp[i][2] = dp[i - 3][0] + dp[i - 3][1];
        }

        return dp[dp.length - 1][0] + dp[dp.length - 1][1] + dp[dp.length - 1][2];
    }


    public static void main(String[] args) {
        LeetCode70Plus leetCode70Plus = new LeetCode70Plus();
        int res = leetCode70Plus.climbStairs(5);
        System.out.println(res);
    }
}
